package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class uniquePaths_ {
  public static void main(String[] args) {
    System.out.println(uniquePaths(3, 7));
  }
  // 1. dp[i][j]表示从(0,0)移动到(i,j)共有dp[i][j]种路径
  // 2. 递推公式: (i,j)可以从(i-1,j)移动到, 可以从(i,j-1)移动到, 故dp[i][j] = dp[i-1][j] + dp[i][j-1]
  // 3. 初始化: 到(i,j)依赖(i-1,j)和(i,j-1), 故需要初始化(0,j)和(i,0
  // 4. 遍历顺序: 到(i,j)可以从(i-1,j)移动到, 可以从(i,j-1)移动到故从左到右遍历, 从上到下遍历
  public static int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++){
      dp[0][j] = 1;
    }
    for (int i = 1 ; i < m;i++){
      for (int j = 1 ; j < n; j++){
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
    return dp[m - 1][n - 1];
  }
}
